#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。



示例 1：


输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：


输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：

输入：matrix = [["0"]]
输出：0*
 * */
int maxcount = 0;

int getMax(vector<vector<char>> &matrix, int row, int col, int &maxRow, int &maxcol) {
    int count = maxcount;   //从这边开始数 1行一列 些许剪枝如果边界小于原来最大的max边界长度就不再寻找了

    int res = 0;

    while (row + count <= maxRow && col + count <= maxcol) {

        for (int i = row; i <= row + count; i++) {
            for (int j = col; j <= col + count; j++) {
                if (matrix[i][j] == '0')
                    goto laber;

            }

        }

        res = (count + 1) * (count + 1);
        count++;

    }

    laber:;

    maxcount = max(maxcount, count);
    return res;

}


int maximalSquare(vector<vector<char>> &matrix) {
    int maxV = 0;
    int rowMax = matrix.size() - 1;
    int colMax = matrix[0].size() - 1;

    for (int i = 0; i <= rowMax; i++) {
        for (int j = 0; j <= colMax; j++) {
            maxV = max(maxV, getMax(matrix, i, j, rowMax, colMax));

        }

    }

    return maxV;

}